#include "algorithm_permutation.h"


/** Vraci, zda zatim dany gen neni v zadnem cyklu.
 * \param index index genu
 * \return true, pokud neni v cyklu
 */
bool PermutationInfo::Empty(int index) {
	return cycle_index[index] == 0;
}

/** Alokuje pamet pro interni potreby.
 * \param size pocet vysilacu
 */
void PermutationInfo::Initialize(int size) {
	position = new int[size];
	cycle_index = new int[size];
	this->size = size;
}

/** Nacte permutaci a ulozi si o ni informace pro jeji rychle zpracovani.
 * \param permutation permutace indexu vysilacu
 */
void PermutationInfo::Load(int * permutation) {
	for (int i = 0; i < size; ++i) {
		position[permutation[i]] = i;
		cycle_index[i] = 0;
	}
}

/** Urci, zda je dany gen v cyklu s lichym indexem.
 * \param index cislo genu (vysilace)
 * \return true, pokud ano
 */
bool PermutationInfo::Odd(int index) {
	return cycle_index[index] % 2 == 1;
}

/** Nastavi danemu genu cislo cyklu.
 * \param value index vysilace
 * \param cycle index cyklu
 */
void PermutationInfo::Set(int value, int cycle) {
	cycle_index[position[value]] = cycle;
}


/** Vyresi problem spustenim permutacniho genetickeho algoritmu. Nejprve vygeneruje nahodne permutace
 * poradi vsech vysilacu, pote je preusporada pomoci algoritmu GSD a nakonec spusti geneticky algoritmus,
 * diky kteremu jsou aktualni reseni neustale vylepsovana (dokud to jde).
 * \return true, pokud se povedlo vytvorit korektni prirazeni frekvenci
 */
bool PermutationAlgorithm::Solve() {
/*	nejdrive vygenerovat nahodne prvotni generaci
	setridit pomoci generalized saturation degree (rovnou i spocitat min span pro kazdy prvek)
	nalezt nejlepsi prvek
	pokud se v poslednich N krocich nezmenilo minimum, tak skoncit, jinak provadet:
		pro kazdy gen - vybrat nahodne druhy gen (pomoci vazeneho vyber)
		pouzit na ne Cycle CrossOver -> jeden novy gen
		ten zmutovat
		-> priradit frekvence
		pokud je lepsi, nez slabsi rodic, pak jej nahradi
			pokud je lepsi nez dosud nejlepsi, tak jej nahradit
*/
	timer->start();
	options->Log() << "1/3 Generovani ";
	options->Display("GENEROVANI");
	Generate();
	options->Log() << timer->lap() << "s" << std::endl;
	// v policku area->size uchovavam hodnotu generace
	// ulozit do frequencies nejaky maximalni odhad (fakt premrsteny))
	frequencies = area->getMaxFrequencies(); /* nejvetsi rozdil * pocet vysilacu */
	best_span = frequencies + 1;
	best = 0;
	ranks = new RankInfo[frequencies];
	options->Log() << "2/3 Generalized Saturation Degree ";
	options->Display("GSD");
	area->save();
	GSDCallList gsd(area, frequencies);
	for (int i = 0; i < options->generation_size; ++i) {
		generation[i][area->size] = GSD(generation[i], gsd);
		if (generation[i][area->size] < best_span) {
			best_span = generation[i][area->size];
			best = i;
		}
		area->load();
	}
	if (best_span == frequencies + 1) return false;
	options->Log() << timer->lap() << "s" << std::endl;
	options->Log() << "3/3 Geneticky algoritmus" << std::endl;
	options->Display("GENETICKY ");
	options->NewDisplay();
	Genetic();
	AssignFrequencies(generation[best]);
	area->save();
	frequencies = best_span;
	for (int i = 0; i < options->generation_size; ++i) {
		delete[] generation[i];
	}
	delete[] generation;
	delete[] ranks;
	options->Log() << "Doba genetickeho algoritmu: " << timer->lap() << std::endl;
	options->Log() << "Celkova doba: " << timer->total() << std::endl;
	return true;
}

/** Spocita poradi vsech reseni podle jejich kvality a soucet poradi. Na zaklade poradi,
 * je pote urcovana pravdepodobnost vyberu reseni na crossover.
 */
void PermutationAlgorithm::CountRanks() {
	int rank = 0;
	int i;
	sum_ranks = 0;
	for (i = 0; i < options->generation_size; ++i) {
		ranks[generation[i][area->size]].positions.push_front(i);
	}
	for (i = best_span; i < frequencies; ++i) {
		if (!ranks[i].positions.empty()) {
			ranks[i].rank = ++rank;
			sum_ranks += (int)(rank * ranks[i].positions.size());
		}
	}
}

/** Vypise do logu poradi vsech reseni.
 */
void PermutationAlgorithm::PrintRanks() {
	int sum = 0;
	options->Log() << "Vysledky genu: " << std::endl;
	for (int i = best_span; i < frequencies; ++i) {
		if (!ranks[i].positions.empty()) {
			sum += (int)ranks[i].positions.size();
			options->Log() << std::setw(5) << i << ": " << ranks[i].positions.size() << std::endl;
		}
	}
	options->Log() << "Soucet ranku: " << sum_ranks << std::endl;
}


/** Zmeni kvalitu daneho reseni a prepocita poradi.
 * \param from puvodni kvalita
 * \param to nova kvalita
 * \param index index meneneho reseni
 */
void PermutationAlgorithm::ChangeRank(int from, int to, int index) {
	int smallest = 1;
	if (to < best_span) {
		best_span = to;
		best = index;
		options->Display(IntToStr(to));
	}
	sum_ranks -= ranks[from].rank;
	ranks[from].positions.remove(index);
	if (ranks[from].positions.empty()) {
		ranks[from].rank = 0;
	}
	for (int i = from; i > to; --i) {
		if (!ranks[i].positions.empty()) {
			sum_ranks += (int)ranks[i].positions.size();
			smallest = (ranks[i].rank)++;
		}
	}
	if (ranks[to].positions.empty()) {
		ranks[to].rank = smallest;
	}
	sum_ranks += ranks[to].rank;
	ranks[to].positions.push_front(index);
}

/** Provadi vyber druheho rodice do crossoveru. Vyber je nahodny s pravdepodobnosti zavislou
 * na poradi reseni mezi vsemi ostatnimi.
 * \return index vybraneho reseni
 */
int PermutationAlgorithm::ChooseSecondParent() {
	int r = RandomNumber(sum_ranks);
	int pos = 0;
	int sz;
	std::list<int>::const_iterator p;
//	options->Log() << "    Hledam pozici " << r << " z " << sum_ranks << ": ";
	for (int i = best_span; i < frequencies; ++i) {
		if (!ranks[i].positions.empty()) {
			sz = (int)(ranks[i].positions.size() * (options->generation_size + 1 - ranks[i].rank));
//			options->Log() << ranks[i].rank << "(P:" << ranks[i].positions.size() << ",H:" << i << ") " << pos << ", ";
			if (pos + sz >= r) {
				/* ve spravnem chlivku */
//				int j = 0;
				for (p = ranks[i].positions.begin(); p != ranks[i].positions.end(); ++p) {
//					++j;
					if ((pos += options->generation_size + 1 - ranks[i].rank) >= r) {
//						options->Log() << " -> vracim |" << j << "| ty prvek z " << ranks[i].positions.size() << std::endl;
						return *p;
					}
				}
				return *(ranks[i].positions.begin());
			}
			else {
				pos += sz;
			}
		}
	} /* kdybych nahodou selhal */
	return options->generation_count - 1;
}

/** Spusti genetickou fazi algoritmu. Algoritmus probiha v krocich. V kazdem kroku jsou vzdy nejdrive
 * provedeno krizeni (prvni rodic je vybran sekvencne, druhy nahodne), potomek je zmutovan, je podle
 * nej prirazen pocet frekvenci a pokud je lepsi, nez slabsi z rodicu, tak jej v populaci nahradi.
 */
void PermutationAlgorithm::Genetic() {
	int change = 0;
	int par1, par2, par_week;
	int * child = new int[area->size + 1], i = 0;
	/* sort the generation according to their fitness */
	CountRanks();
	PrintRanks();
	int part_count = 6;

	options->Log() << "Generation;Start frequency;Changes;" << std::endl;
	while (change < options->generation_count) {
//		options->Log() << " --- " << ++i << ". GENERACE, posledni zmena pred " << change << ", nejlepsi: " << best_span << " ---" << std::endl;
		options->Log() << i << ";";
		++change;
		int change_count = 0;
		for (par1 = 0; par1 < options->generation_size; ++par1) {
			par2 = ChooseSecondParent(); // todo
			CrossOver(generation[par1], generation[par2], child);
			if (generation[par1][area->size] <= generation[par2][area->size]) par_week = par2;
			else par_week = par1;
			Mutate(child);
			child[area->size] = AssignFrequencies(child);
//			options->Log() << " Otcove: " << par1 << " (" << generation[par1][area->size] << "), " << par2 << " (" << generation[par2][area->size] << "), dite: " << child[area->size] << std::endl;
			if (child[area->size] < generation[par_week][area->size]) {
				++change_count;
				// options->Log() << " Nahrazuji otce " << par_week << " (" << generation[par_week][area->size] <<  ") synem s hodnotou " << child[area->size] << std::endl;
				change = 0;
				ChangeRank(generation[par_week][area->size], child[area->size], par_week);
				std::swap(generation[par_week], child);
			}
			area->load();
		}
		options->Log() << best_span << ";" << change_count << ";" << std::endl;
	}
}

/** Cyklicky crossover (krizeni reseni). Vice na http://www.oxypedia.org/Cycle-Crossover-01.htm .
 * \param p1 prvni rodic
 * \param p2 druhy rodic
 * \param child potomek, vystupni parametr
 */
void PermutationAlgorithm::CrossOver(int * p1, int * p2, int * child) {
	/* cycle crossover - from http://www.oxypedia.org/Cycle-Crossover-01.htm */
	perm_info.Load(p1);
	int cycle = 1;
	int j, i;
	for (i = 0; i < area->size; ++i) {
		if (perm_info.Empty(i)) {
			j = p2[i];
			perm_info.Set(j, cycle);
			while (j != p1[i]) {
				j = p2[perm_info.position[j]];
				perm_info.Set(j, cycle);
			}
			++cycle;
		}
	}
	for (i = 0; i < area->size; ++i) {
		child[i] = (perm_info.Odd(i) ? p1[i] : p2[i]);
	}
}

/** Provede mutaci daneho reseni. Mutace je zde prohozeni pozic dvou vysilacu.
 * \param individual mutovane reseni
 */
void PermutationAlgorithm::Mutate(int * individual) {
	/* just swap two random positions */
	if (area->size <= 1) return;
	int pos1, pos2;
	pos1 = RandomNumber(area->size);
	do {
		pos2 = RandomNumber(area->size);
	} while (pos1 == pos2);
	std::swap(individual[pos1], individual[pos2]);
}

/** Nahodne vygeneruje pocatecni populaci reseni.
 */
void PermutationAlgorithm::Generate() {
	int * call_list;
	call_list = new int[area->size + 1];
	generation = new int *[options->generation_size];
	for (int i = 0; i < area->size; ++i) {
		call_list[i] = i;
	}
	call_list[area->size] = -1;
	generation[0] = MixArray(call_list);
	for (int i = 1; i < options->generation_size; ++i) {
		generation[i] = MixArray(generation[i - 1]);
	}
	delete[] call_list;
}

/** Nahodne zamicha predane pole.
 * \param a pole k promichani
 */
int * PermutationAlgorithm::MixArray(int * a) {
	int * mixed = new int[area->size + 1];
	for (int i = 0; i < area->size; ++i) {
		mixed[i] = a[i];
	}
	int i, j;
	for (int changes = RandomNumber(area->size * 10, area->size); changes > 0; --changes) {
		i = RandomNumber(area->size);
		j = RandomNumber(area->size);
		std::swap(mixed[i], mixed[j]);
	}
	return mixed;
}

/** Pomoci sekvencniho algoritmu priradi frekvence vsem vysilacum v zadanem poradi. Pouzivano pro
 * vyhodnoceni kvality reseni (to je prave to poradi vysilacu).
 * \param call_list poradi vysilacu (permutace)
 * \return sirka pouziteho frekvencniho pasma
 */
int PermutationAlgorithm::AssignFrequencies(int * call_list) {
	int span = 0;
	bool fail;
	int cell;
	for (int i = 0; i < area->size; ++i) {
		if (area->calls[call_list[i]] != 0) continue;
		//	GSD(call_list + i, size - i, positions); // prerovna cally tak, aby byl volany vzdy ten nejblizsi
		fail = true;
		cell = -1;
		area->findCell(call_list[i], cell);
		if (area->cell_min[cell] < 1) options->Log() << "ERROR MINCELL" << std::endl;
		for (int f = area->cell_min[cell]; f <= frequencies; ++f) {
			if (area->assignCall(call_list[i], f, cell)) {
				if (f > span) span = f;
				fail = false;
				break;
			}
		}
		if (fail) return(frequencies + 1);
	}
	return span;
}

/** Algoritmus vazeneho stupne nasyceni. Preusporada algoritmem GSD zadanou permutaci vysilacu a\
 * spocte sirku pouziteho pasma.
 * \param call_list permutace vysilacu
 * \param info pomocna datova struktura pro ukladani informaci o permutaci
 */
int PermutationAlgorithm::GSD(int * call_list, GSDCallList & info) {
	/* generalized saturation degree */
	bool fail;
	int cell;
	info.initialize(call_list);
	options->Log() << "GSD posloupnost: ";
	while (info.getNext()) {
		options->Log() << std::setw(5) << info.getCurrent();
		fail = true;
		cell = -1;
		area->findCell(info.getCurrent(), cell);
		for (int f = 1; f <= frequencies; ++f) {
			if (area->assignCall(info.getCurrent(), f, cell)) {
				info.assign(f);
				fail = false;
				break;
			}
		}
		if (fail) return frequencies + 1;
	}
	options->Log() << std::endl;
	return info.getSpan();
}


/** Vypise do logu vsechna reseni v zadane populaci.
 * \param generation populace vsech reseni
 * \param size pocet vysilacu
 */
void PermutationAlgorithm::PrintGeneration(int ** generation, int size) {
	options->Log() << "Vypis generace: " << std::endl;
	for (int i = 0; i < options->generation_size; ++i) {
		options->Log() << std::setw(4) << i + 1 << " | ";
		for (int j = 0; j < size; ++j) {
			options->Log() << std::setw(4) << generation[i][j];
		}
		options->Log() << std::endl;
	}
}
